package gold.gold02;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *
 */
public class S0408首个共同祖先 {
    /**
     * 100, 这个很有参考价值。
     * 后序遍历, 发现左右两边都是有目标节点的话就把自己网上抛, 自己是目标节点也把自己网上抛,
     * 只有一个子树带目标节点就把子树返回值网上抛, 否则抛null。
     *
     * 返回节点只是表示这里有p或者q, 节点里面是多少不重要。
     * 左右两边都是有pq节点的话, 需要把当前节点传到根节点, 所以如果左右只有一个有pq的话,
     * 是传有pq的那个子节点而不是自己, 这个在两个节点相遇之前没用, 在相遇之后, 首个共同祖先
     * 传递到根节点的路上有用。
     */
    // root肯定为他的共同祖先, 然后递归看看左子树是不是共同祖先, 右子树是不是, 最后就是第一个共同祖先
    // 但是这样复杂度比较高?记一下root到两者的路径, 然后比较两个数组的最后一个共同值?
    // 懂了, 有p或者q的是有效的, 第一个祖先就是左边和右边都是有p有q的。
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val == p.val || root.val == q.val) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null){
            if(right == null){
                return null;
            }else{
                return right;
            }
        }else{
            if(right == null){
                return left;
            }else{
                return root;
            }
        }
    }

    /**
     * 和我的类似, 不过是返回boolean, 注意一个情况, 就是p是q的根节点这种情况, 在上面一种方法中这种情况被覆盖了, 其实是需要考虑的。
     */
    private TreeNode ans;

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }


    /**
     * 存储节点也很重要, 这种一般是用set
     * 这里相当于用Map中的一堆键值对存储了每个节点的访问路径, 可以学习
     */
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            // 存储的是子树val和其父节点
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        // visited中是p到root的路径
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        // 从q逐个网上找, 找到在p路径中的值, 那此时的p就是首个根节点
        // 这里用set存储路径, 来找交点; 用Map存储路径, 这两种方式不错。
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }


}
